package BasicDataStructures;

import java.util.LinkedList;
import java.util.List;

/**
 * 用拉链法实现哈希表
 * @param <k> key
 * @param <v> value
 */

public class MyChainingHashMap<k,v> {


    private static class KVNode<k,v> {
        k key;
        v value;

        KVNode(k key,v value){
            this.key = key;
            this.value = value;
        }
    }

    //申明一个哈希表底层的数组，数组中元素类型为链表
    private LinkedList<KVNode<k,v>>[] table;

    //哈希表中存入的键值对个数
    private int size;

    //底层数组的初始容量
    private static final int INIT_CAP = 4;

    public MyChainingHashMap(){
        this(INIT_CAP);
    }

    public MyChainingHashMap(int initCap) {
        size = 0;
        // 保证底层数组的容量至少为 1，因为 hash 函数中有求余运算，避免出现除以 0 的情况
        initCap = Math.max(initCap,1);
        //先申明一个链表，再强转为LinkedList<KVNode<k,v>>[]数组类型
        table = (LinkedList<KVNode<k,v>>[])new LinkedList[initCap];

        for (int i = 0; i < table.length; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 添加 key -> val 键值对
    // 如果键 key 已存在，则将值修改为 val
    public void put(k key , v value) {
        //key值非法
        if (key == null){
            throw new IllegalStateException("key is null");
        }

        LinkedList<KVNode<k,v>> list = table[hash(key)];
        // 如果 key 之前存在，则修改对应的 val
        for (KVNode<k, v> node : list) {
            if (node.key.equals(key)){
                node.value = value;
                return;
            }
        }

        // 如果 key 之前不存在，则插入，size 增加
        list.add(new KVNode<>(key, value));
        size++;

        if (size >= table.length * 0.75) {
            resize(2 * table.length);
        }
    }

    // 删除 key 和对应的 val
    public void remove(k key) {
        if (key == null) {
            throw new IllegalStateException("key is null");
        }

        LinkedList<KVNode<k,v>> list = table[hash(key)];

        if (list == null) {
            return;
        }

        for (KVNode<k, v> kvNode : list) {
            if (kvNode.key.equals(key)){
                list.remove(kvNode);
                size--;

                // 缩容，当负载因子小于 0.125 时，缩容
                if (size <= table.length / 8) {
                    resize(table.length / 4);
                }
                return;
            }
        }
    }

    // 返回 key 对应的 val，如果 key 不存在，则返回 null
    public v get(k key) {
        if (key == null) {
            throw new IllegalStateException("key is null");
        }

        LinkedList<KVNode<k,v>> list = table[hash(key)];
        for (KVNode<k, v> kvNode : list) {
            if (kvNode.key.equals(key)) {
                return kvNode.value;
            }
        }

        return null;
    }

    //返回所有 key
    public List<k> keys() {
        List<k> keys = new LinkedList<>();

        for (LinkedList<KVNode<k, v>> list : table) {
            for (KVNode<k, v> kvNode : list) {
                keys.add(kvNode.key);
            }
        }

        return keys;
    }

    // 哈希函数，将键映射到 table 的索引
    private int hash(k key) {
        return (key.hashCode() & 0x7fffffff) % table.length;
    }

    private void resize(int newCap){
        newCap = Math.max(newCap,1);

        //创建一个新Map
        MyChainingHashMap<k,v> newMap = new MyChainingHashMap<>(newCap);

        //遍历所有node,将他们重新放入Map中
        for (LinkedList<KVNode<k, v>> list : table) {
            for (KVNode<k, v> kvKVNode : list) {
                newMap.put(kvKVNode.key, kvKVNode.value);
            }
        }

        this.table = newMap.table;
    }

    public static void main(String[] args) {
        MyChainingHashMap<Integer, Integer> map = new MyChainingHashMap<>();
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        System.out.println(map.get(1)); // 1
        System.out.println(map.get(2)); // 2

        map.put(1, 100);
        System.out.println(map.get(1)); // 100

        map.remove(2);
        System.out.println(map.get(2)); // null
        // [1, 3]（顺序可能不同）
        System.out.println(map.keys());

        map.remove(1);
        map.remove(2);
        map.remove(3);
        System.out.println(map.get(1)); // null
    }
}
